<HTML>
<HEAD>
<TITLE>Postman</TITLE>
</head>

<body>

<center>
<h1>BOI 2001 Day 1 Problem 1</h1>
<H1>Postman</H1>
</center>

<p>
In a countryside a postman has to deliver post to customers  that live in villages and along every road connecting the villages.</p>
<p>
Your task is to help the postman  design a route that goes though every village and every road  at least once--the input data are such that this is always  possible.
However, each route also has a cost.
The people in the villages wish that the postman  visit their village as early as possible.
Therefore, each village has made the following deal with the post:  If the village <i>i</i> is visited as the <i>k</i>-th different  village on the tour and <i>k&lt;=w(i)</i>, the village pays <i>w(i)-k</i>  euros to the post.
However, if <i>k&gt;w(i)</i>, the post agrees to pay <i>k-w(i)</i> euros  to the village.
Moreover, the post pays the postman one euro for each road on the  tour.</p>

<p>There are <i>n</i> villages, numbered form 1 to <i>n</i>.
The post is located in the village number one, so the route should  start and end in this village.
Each village is placed on the crossing of  two roads, on the crossing of four roads,  or there is a road going through the village  (i.e.
there are 2, 4, or 8 roads going out of each village).
There can be several roads connecting the same villages or a road  can be a loop, i.e.
connect a village with itself.

<h2>Task</h2>

<p>  Your task is to write a program that:  
<ul>  
<li> reads the description of villages and connecting them  roads, from the input file <tt>pos.in</tt>,   
<li>  designs such a route that goes through each village and road  at least once and maximizes the total profit (or minimizes  the loss) of the post,  
<li> writes the result to the output file <tt>pos.out</tt>.
</ul>
<p>
  If there are several possible solutions, your program should  output just one of them.

<h2>Input</h2>

<p>  In the first line of the input file <tt>pos.in</tt>, there are two  integers <i>n</i> and <i>m</i>, separated by  a single space;  <i>n</i>, <i>1&lt;=n&lt;=200</i>, is the number of villages and <i>m</i> is the number of roads.
In each of the following <i>n</i> lines there is one positive  integer.
The <i>i+1</i>-th line contains <i>w(i)</i>, <i>1&lt;=w(i)&lt;=1&nbsp;000</i>,  specification of the fee paid by the village number <i>i</i>.
In each of the following <i>m</i> lines there are two positive  integers separated by a single space--villages connected by  consecutive roads.

<h2>Output</h2>

<p>  Your program should write one positive integer <i>k</i>, the length  of the route, to the first line of the output file <tt>pos.out</tt>.
The following line should contain <i>k+1</i> numbers of consecutive  villages on the route  <i>v<sub>1</sub>,v<sub>2</sub>,...,v<sub>k+1</sub></i>, separated by single spaces, with  <i>v<sub>1</sub>=v<sub>k+1</sub>=1</i>.</p>

<img src="image/278.gif">  

<h2>Sample Input</h2>
<pre>
6 7
1
7
4
10
20
5
2 4
1 5
2 1
4 5
3 6
1 6
1 3
</pre>

<h2>Sample Output</h2>
<pre>
7
1 5 4 2 1 6 3 1
</pre>
</body>
</html>
